package com.xuwei.base.sort;
/**
 * 插入排序
 * @author David
 *
 */
public class InsertSort
{
	//插入排序方法
	public static void sort(int arr[])
	{
		for(int i=1;i<arr.length;i++)
		{
			int insertVal=arr[i];
			//insertVal准备和前一个数比较
			int index=i-1;
			while(index>=0&&insertVal<arr[index])
			{
				//把arr[index]向后移动
				arr[index+1]=arr[index];
				//让index向前移动一位
				index--;
				
			}
			//将insertVal插入适当位置
			arr[index+1]=insertVal;
		}
	}
}
